package alo.p12.work;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

import static java.util.Arrays.sort;

/**
 * @ClassName BFPTR
 * @Description 中位数的中位数算法
 * @Author Fanxc
 * @DATE 2021/3/14 11:46
 * @Version 1.0
 */
public class BFPTR {
    //交换
    void swap(int a,int b){
        int temp;
        temp=a;
        a=b;
        b=temp;
    }

    //插入排序
    void InsertSort(int[] a, int l, int r)
    {
        for(int i = l + 1; i <= r; i++)
        {
            if(a[i - 1] > a[i])
            {
                int t = a[i];
                int j = i;
                while(j > l && a[j - 1] > t)
                {
                    a[j] = a[j - 1];
                    j--;
                }
                a[j] = t;
            }
        }
    }

    //寻找中位数的中位数
    int FindMid(int[] a, int l, int r)
    {
        if(l == r) return a[l];
        int i;
        int n = 0;
        for(i = l; i < r - 5; i += 5)
        {
            InsertSort(a, i, i + 4);
            n = i - l;
            swap(a[l + n / 5], a[i + 2]);
        }

        //处理剩余元素
        int num = r - i + 1;
        if(num > 0)
        {
            InsertSort(a, i, i + num - 1);
            n = i - l;
            swap(a[l + n / 5], a[i + num / 2]);
        }
        n /= 5;
        if(n == l) return a[l];
        return FindMid(a, l, l + n);
    }

    //寻找中位数的所在位置
    int FindId(int[] a, int l, int r, int num)
    {
        for(int i = l; i <= r; i++)
            if(a[i] == num)
                return i;
        return -1;
    }

    //进行划分过程
    int Partition(int[] a, int l, int r, int p)
    {
        swap(a[p], a[l]);
        int i = l;
        int j = r;
        int pivot = a[l];
        while(i < j)
        {
            while(a[j] >= pivot && i < j)
                j--;
            a[i] = a[j];
            while(a[i] <= pivot && i < j)
                i++;
            a[j] = a[i];
        }
        a[i] = pivot;
        return i;
    }

    int BFPTR(int[] a, int l, int r, int k)
    {
        int num = FindMid(a, l, r);    //寻找中位数的中位数
        int p =  FindId(a, l, r, num); //找到中位数的中位数对应的id
        int i = Partition(a, l, r, p);

        int m = i - l + 1;
        if(m == k) return a[i];
        if(m > k)  return BFPTR(a, l, i - 1, k);
        return BFPTR(a, i + 1, r, k - m);
    }


    @Test
    public void test(){
        int[] a=new int[11];
        Random random=new Random();
        for(int i=0;i<a.length;i++)
            a[i]=random.nextInt(101);  //随机生成10个0到100的数字
        System.out.println("生成的结果是："+ Arrays.toString(a));
        int secondMax = BFPTR(a,0,10,5);
        System.out.println("第五大的数是："+secondMax);
        sort(a);
        System.out.println("生成的结果是："+ Arrays.toString(a));
    }
}
